package phylogenetictree;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Random;

import javax.swing.JFrame;

import org.apache.commons.lang3.StringUtils;

import searchTree.searchTreeNode;

import Algorthim.Algorithim;

import com.rits.cloning.Cloner;

public class PhylogeneticTree {
	private ArrayList<Integer>[] adjacencyList;
	public Map<Integer,String> indexMap;
	private ArrayList<Integer> leafs;
	private Integer nodeNum = 0;
//	private int leafOffset;
	
	public int getSize() {
		return indexMap.size();
	}

	// should change to a singleton pattern or object pool
	private Cloner cloner = new Cloner(); 
	private Random random = new Random();
	
	public ArrayList<Integer> getleafs()
	{
		return this.leafs;
	}
	
	/*
	 * creates a random tree with the specified number of nodes
	 */
	@SuppressWarnings("unchecked")
	public PhylogeneticTree(int numberOfLeafs)
	{
//		numberOfLeafs += 2;
		adjacencyList = (ArrayList<Integer>[])new ArrayList[numberOfLeafs+(numberOfLeafs - 2)+1];
		indexMap = new HashMap<Integer, String>();
		initiliseAdjacenyList();
		this.leafs = new ArrayList<Integer>();
		
		// create two starting nodes
		indexMap.put(nodeNum, "Node : " + nodeNum);
		leafs.add(nodeNum);
		Integer nodeOne = nodeNum;
		nodeNum++;
		indexMap.put(nodeNum, "Node : " + nodeNum);
		leafs.add(nodeNum);
		this.addEdge(nodeOne, nodeNum);
		nodeNum++;
		
		int randomOne;
		int randomother;
		for(int i = 2; i < numberOfLeafs; i++)
		{
			randomOne = random.nextInt(nodeNum);
			
			randomother = adjacencyList[randomOne].get(random.nextInt(adjacencyList[randomOne].size()));
			
			this.removeEdge(randomOne, randomother);
			
			Integer joiner = nodeNum;
			indexMap.put(joiner, "" + nodeNum);			
			nodeNum++;
			indexMap.put(nodeNum, "Node : " + nodeNum);
			leafs.add(nodeNum);
			Integer newLeaf = nodeNum;
			nodeNum++;
			
			this.addEdge(joiner, randomother);
			this.addEdge(joiner, randomOne);
			this.addEdge(joiner, newLeaf);
		}
	}
	
	@SuppressWarnings("unchecked")
	public PhylogeneticTree(String file) throws IOException
	{
		Map<String,Integer> nodeindexMap = new HashMap<String, Integer>();
		BufferedReader input =  new BufferedReader(new FileReader(file));
		this.leafs = new ArrayList<Integer>();
		String[] leafs = input.readLine().split(",");
		String[] links = input.readLine().split(",");
		
		int numberOfLeafs = leafs.length + 1;
		adjacencyList = (ArrayList<Integer>[])new ArrayList[numberOfLeafs+(numberOfLeafs - 2) + 1];
		indexMap = new HashMap<Integer, String>();
		initiliseAdjacenyList();
		
		for(String leaf:leafs)
		{
			indexMap.put(nodeNum, leaf);
			nodeindexMap.put(leaf, nodeNum);
			this.leafs.add(nodeNum);
			nodeNum++;			
		}
		for(String link:links)
		{
			String[] ends = link.split("-");
			if(nodeindexMap.get(ends[0]) == null)
			{
				indexMap.put(nodeNum, ends[0]);
				nodeindexMap.put(ends[0], nodeNum);
				nodeNum++;
			}
			if(nodeindexMap.get(ends[1]) == null)
			{
				indexMap.put(nodeNum, ends[1]);
				nodeindexMap.put(ends[1], nodeNum);
				nodeNum++;
			}
			this.addEdge(nodeindexMap.get(ends[0]), nodeindexMap.get(ends[1]));
		}
		
		this.removepointlessVertexs();	
	}
	
	public PhylogeneticTree createMutant(int TBR)
	{
		PhylogeneticTree newTree = cloner.deepClone(this);
		newTree.adjacencyList = (ArrayList<Integer>[])new ArrayList[this.adjacencyList.length + TBR*2];
		for(int i = 0; i < this.adjacencyList.length;i++)
		{
			newTree.adjacencyList[i] = cloner.deepClone(this.adjacencyList[i]);
		}
		for(int i = this.adjacencyList.length; i < newTree.adjacencyList.length;i++)
		{
			newTree.adjacencyList[i] = new ArrayList<Integer>();
		}
		
		ArrayList<Integer[]> modded = new ArrayList<Integer[]>();
		for(int i = 0; i < TBR; i++)
		{
			ArrayList<Integer> guessList = new ArrayList<Integer>();
			for(int index = 0; index < this.adjacencyList.length; index++)
			{
				if(this.adjacencyList[index] != null)
				{
					guessList.add(index);
				}
			}
			
			// remove edge
			Integer firstRand;
			Integer secoundRand;
			do
			{
				do
				{
					firstRand = guessList.get(random.nextInt(guessList.size()));
					guessList.remove(firstRand);
				} while(newTree.getNodeConnections(firstRand) == null || newTree.getNodeConnections(firstRand).size() == 0);
				
				secoundRand = newTree.getNodeConnections(firstRand).get(random.nextInt(newTree.getNodeConnections(firstRand).size()));
			} while(modded.contains(new Integer[]{firstRand,secoundRand}));
			modded.add(new Integer[]{firstRand,secoundRand});
			modded.add(new Integer[]{secoundRand,firstRand});
			
			newTree.removeEdge(firstRand, secoundRand);
//			System.out.println(newTree.indexMap.get(firstRand) + " conection with " + newTree.indexMap.get(secoundRand) + " was Cut");
			
			guessList = new ArrayList<Integer>();
			for(int index = 0; index < newTree.adjacencyList.length; index++)
			{
				guessList.add(index);
			}
			
			// find reattachment points
			Integer newJoinOne = null;
			do
			{
//				if(guessList.size() == 0)
//				{
//					i--;
//					newTree.addEdge(firstRand, secoundRand);
//					continue;
//				}
				if(guessList.size() == 1)
				{
					newJoinOne = guessList.get(random.nextInt(1)); // need to fix properly as will screw some trees
				}
				else
				{
					newJoinOne = guessList.get(random.nextInt(guessList.size()));
				}
				guessList.remove(newJoinOne);
			}while(!newTree.DoesNodeExcist(newJoinOne) || !connected(newTree,firstRand, -1, newJoinOne));
			
			
			guessList = new ArrayList<Integer>();
			for(int index = 0; index < newTree.adjacencyList.length; index++)
			{
				guessList.add(index);
			}
			
			Integer newJoinTwo;
			do
			{
				if(guessList.size() == 1)
				{
					newJoinTwo = guessList.get(random.nextInt(guessList.size()));
				}
				else
				{
					newJoinTwo = guessList.get(random.nextInt(guessList.size()));
				}
				guessList.remove(newJoinTwo);
			}while(!newTree.DoesNodeExcist(newJoinTwo) || !connected(newTree,secoundRand, -1, newJoinTwo));
			
			Integer joinerOne; // 
			// reattach 
			if(newTree.getNodeConnections(newJoinOne).size() == 0)
			{
				// just attach directly
				joinerOne = newJoinOne;
			}
			else
			{
				Integer otherOne = newTree.getNodeConnections(newJoinOne).get(random.nextInt(newTree.getNodeConnections(newJoinOne).size()));
				joinerOne = nodeNum;
				newTree.indexMap.put(joinerOne, "New Node : " + nodeNum);
				nodeNum++;
				newTree.removeEdge(newJoinOne, otherOne);
				
				newTree.addEdge(joinerOne, otherOne);
				newTree.addEdge(newJoinOne, joinerOne);
//				System.out.println(newTree.indexMap.get(joinerOne) + " joined to " + newTree.indexMap.get(otherOne) + " and " + newTree.indexMap.get(newJoinOne));
			}
			
			Integer joinerTwo;
			if(newTree.getNodeConnections(newJoinTwo).size() == 0)
			{
				// just attach directly
				joinerTwo = newJoinTwo;
			}
			else
			{
				Integer otherTwo = newTree.getNodeConnections(newJoinTwo).get(random.nextInt(newTree.getNodeConnections(newJoinTwo).size()));
				joinerTwo = nodeNum;
				newTree.indexMap.put(joinerTwo, "New Node : " + nodeNum);
				nodeNum++;
				newTree.removeEdge(newJoinTwo, otherTwo);
				
				newTree.addEdge(joinerTwo, otherTwo);
				newTree.addEdge(newJoinTwo, joinerTwo);
//				System.out.println(newTree.indexMap.get(joinerTwo) + " joined to " + newTree.indexMap.get(otherTwo) + " and " + newTree.indexMap.get(newJoinTwo));
			}
			
			newTree.addEdge(joinerOne, joinerTwo);
//			System.out.println(newTree.indexMap.get(joinerOne) + " joined to " + newTree.indexMap.get(joinerTwo));
			
			newTree.removepointlessVertexs();
		}
		
		return newTree;
	}
	
	
	public boolean DoesNodeExcist(int index)
	{
		return this.adjacencyList[index] != null;
	}
	
	public boolean isLeaf(Integer index)
	{
		return this.leafs.contains(index);
	}
	
	public boolean removeEdge(Integer a, Integer b)
	{
		boolean result = false;
		result = this.adjacencyList[a].remove(new Integer(b));
		if(!result)
		{
			return false;
		}
		return this.adjacencyList[b].remove(new Integer(a));
	}
	
	private void addEdge(Integer a,Integer b)
	{
		this.adjacencyList[a].add(b);
		this.adjacencyList[b].add(a);
	}
	
	public String toCommaSeperatedFile()
	{
		String result = "";
		for(Integer i = 0;i < adjacencyList.length;i++)
		{
			if(this.isLeaf(i))
			{
				if(result.length() == 0)
				{
					result += indexMap.get(i);
				}
				else
				{
					result += "," + indexMap.get(i);
				}
			}
		}
		
		result += "\n";
		boolean first = true;
		
		for(int i = 0; i < adjacencyList.length;i++)
		{
			if(this.getNodeConnections(i) == null)
			{
				continue;
			}
			for(Integer linked:this.getNodeConnections(i))
			{
				String test = indexMap.get(i) + "-" + indexMap.get(linked);
				String testTwo = indexMap.get(linked) + "-" + indexMap.get(i);
				if(!StringUtils.contains(result, test) && !StringUtils.contains(result, testTwo))
				{
					if(first)
					{
						first = false;
						result += test;
					}
					else
					{
						result += "," + test;
					}
				}
			}
		}
		
		return result;
	}
	
	public void removepointlessVertexs()
	{
		Boolean Changed = true;
		while(Changed)
		{
			Changed = false;
			for(int i = 0;i < this.adjacencyList.length; i++)
			{
				ArrayList<Integer> list = this.adjacencyList[i];
				if(list == null)
				{
					continue;
				}
				if(list.size() == 1 && !isLeaf(i))
				{
					for(int index = 0; index < list.size(); index++)
					{
						this.removeEdge(i, list.get(index));
						Changed = true;
						this.adjacencyList[i] = null;
						this.indexMap.remove(i);
					}
				}
				else if(list.size() == 2 && !isLeaf(i))
				{
					int sideOne = list.get(0);
					int sideTwo = list.get(1);
					this.removeEdge(i, sideOne);
					this.removeEdge(i, sideTwo);
					
					this.addEdge(sideOne, sideTwo);
					this.adjacencyList[i] = null;
					this.indexMap.remove(i);
					
					Changed = true;
				}	
			}
		}
	}
	
	public ArrayList<Integer> getNodeConnections(int index)
	{
		return this.adjacencyList[index];
	}
	
	public static Boolean connected(PhylogeneticTree tree,Integer start,Integer parent,Integer search)
	{
		if(start.equals(search))
		{
			return true;
		}
		
		for(Integer child:tree.getNodeConnections(start))
		{
			if(parent == -1 || !child.equals(parent))
			{
				Boolean result = connected(tree,child, start, search);
				if(result)
				{
					return result;
				}
			}
		}
		return false;
	}
	
	public static Integer getleaf(PhylogeneticTree tree,Integer start,Integer parent)
	{
		if(tree.isLeaf(start))
		{
			return start;
		}
		
		for(Integer child:tree.getNodeConnections(start))
		{
			if(parent == -1 || !child.equals(parent))
			{
				Integer result = getleaf(tree,child, start);
				if(result != null)
				{
					return result;
				}
			}
		}
		return -1;
	}
	
	private void initiliseAdjacenyList()
	{
		for(int i =0; i < this.adjacencyList.length; i++)
		{
			this.adjacencyList[i] = new ArrayList<Integer>();
		}
	}
	
	public Integer getleaf()
	{
		return this.leafs.get(0);
	}
	
	public ArrayList<Integer>[] getAdjacencyList() {
		return adjacencyList;
	}

	public void kernelise(PhylogeneticTree treeTwo)
	{
		
	}
	
	public static void main(String[] args)
	{
//		try {
			PhylogeneticTree tree = new PhylogeneticTree(100);
			PhylogeneticTree mutant = tree.createMutant(5);
//			tree.removepointlessVertexs();
//			Forest myForest = new Forest(tree);
			
//			Algorithim myAlg = new Algorithim() {
//				
//				@Override
//				protected void handlePhaseOneReturn(searchTreeNode node,
//						Integer firstleaf, Integer firstJunction,
//						Integer secoundleaf, Integer secoundJunction,
//						Integer thirdleaf, Integer forthleaf) {
//					// TODO Auto-generated method stub
//					
//				}
//
//				@Override
//				protected void handlePhaseOneComplete(searchTreeNode node) {
//					// TODO Auto-generated method stub
//					
//				}
//
//				@Override
//				protected void handlePhaseTwoReturn(searchTreeNode node,
//						Integer[] edgeOne, Integer[] edgeTwo) {
//					// TODO Auto-generated method stub
//					
//				}
//			};
			
//			myAlg.setGlobalData(new myAlg.buildPathMap(tree),myAlg.buildPathMap(mutant),new ArrayList<searchTreeNode>());
			
//			ArrayList<Integer[]> results = myAlg.getInternalEdgesWithGuards(0, -1, tree);
//			for(Integer[] result:results)
//			{
//				System.out.println("internal edge" + tree.indexMap.get(result[0]) + "," + tree.indexMap.get(result[3]) + " Guards " + tree.indexMap.get(result[1]) + "," + tree.indexMap.get(result[2]));
//			}
//			
			JFrame dialog = new JFrame("mutant");
			dialog.setContentPane(GUI.TreeDisplayer.treeVeiwer(mutant));
			dialog.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
			dialog.pack();
			dialog.setVisible(true);
			
//			JFrame dialogTwo = new JFrame("tree Two");
//			dialogTwo.setContentPane(GUI.Example.treeVeiwer(mutant));
//			dialogTwo.pack();
//			dialogTwo.setVisible(true);

			
//			System.out.println(connected(tree,0, -1, 5));
//			System.out.println(tree.toCommaSeperatedFile());
//			System.out.println();
//			System.out.println(mutant.toCommaSeperatedFile());
//		} catch (IOException e) {
//			// TODO Auto-generated catch block
//			e.printStackTrace();
//		}
	}
}
